package puzzle.nurikabe.data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import puzzle.common.point.Direction;
import puzzle.common.point.Pnt;
import tomoto.util.ArrayUtil;
import tomoto.util.CollectionUtil;
import tomoto.util.NumberUtil;

public class ShimaPotential {
	private int m_number;
	private int m_tableCener;
	private int m_tableWidth;
	private Pnt m_lefttop;
	private Pnt m_rightbottom;
	private int[] m_potentialTable;
	private int m_possibleArea;
	// private int[] m_cellsPerPotential;
	private List<Pnt>[] m_cellsPerPotential;
	
	@SuppressWarnings("unchecked")
	private List<Pnt>[] newPointListArray(int length) {
		return new List[length];
	}

	public ShimaPotential(int n, int x0, int y0, int x1, int y1) {
		m_number = n;
		m_tableWidth = m_number * 2 - 1;
		m_tableCener = m_tableWidth * m_tableWidth / 2;
		m_lefttop = new Pnt(x0, y0);
		m_rightbottom = new Pnt(x1, y1);

		m_potentialTable = new int[m_tableWidth * m_tableWidth];
		m_possibleArea = 0;

		// m_cellsPerPotential = new int[m_number];
		m_cellsPerPotential = newPointListArray(m_number);
		for (int i = 0; i < m_number; i++) {
			m_cellsPerPotential[i] = new ArrayList<Pnt>();
		}

		initPotentialTable();
	}

	public ShimaPotential(ShimaPotential other) {
		m_number = other.m_number;
		m_tableWidth = other.m_tableWidth;
		m_tableCener = other.m_tableCener;
		m_lefttop = other.m_lefttop;
		m_rightbottom = other.m_rightbottom;

		m_potentialTable = ArrayUtil.dup(other.m_potentialTable);
		m_possibleArea = other.m_possibleArea;

		m_cellsPerPotential = newPointListArray(m_number);
		for (int i = 0; i < m_number; i++) {
			m_cellsPerPotential[i] = new ArrayList<Pnt>(other.m_cellsPerPotential[i]);
		}
	}

	public ShimaPotential dup() {
		return new ShimaPotential(this);
	}

	private boolean setPotential(int x, int y, int n) {
		if (!inRange(x, y)) {
			return false;
		}

		int i = x + y * m_tableWidth + m_tableCener;
		int n0 = m_potentialTable[i];
		if (n0 != n) {
			m_potentialTable[i] = n;
			if (n0 != 0) {
				m_cellsPerPotential[n0 - 1].remove(new Pnt(x, y));
				m_possibleArea--;
			}
			if (n != 0) {
				m_cellsPerPotential[n - 1].add(new Pnt(x, y));
				m_possibleArea++;
			}
			return true;
		} else {
			return false;
		}
	}

	private void initPotentialTable() {
		for (int i = 1; i <= m_number; i++) {
			initPotentialTableLayer(m_number - i, i);
		}
		setPotential(0, 0, m_number);
	}

	private void initPotentialTableLayer(int radius, int n) {
		for (int i = 0; i < radius; i++) {
			setPotential(+i, -radius + i, n);
			setPotential(+radius - i, +i, n);
			setPotential(-i, radius - i, n);
			setPotential(-radius + i, -i, n);
		}
	}

	private boolean inRange(int x, int y) {
		return x >= m_lefttop.x && x <= m_rightbottom.x && y >= m_lefttop.y && y <= m_rightbottom.y;
	}

	public int getPotential(int x, int y) {
		if (inRange(x, y)) {
			return m_potentialTable[x + y * m_tableWidth + m_tableCener];
		} else {
			return 0;
		}
	}

	public boolean updatePotential(int x, int y, int n) {
		int n0 = getPotential(x, y);
		if (n0 != n) {
			assert n < n0;
			setPotential(x, y, n);
			validate(x, y - 1, n0);
			validate(x + 1, y, n0);
			validate(x, y + 1, n0);
			validate(x - 1, y, n0);
			return true;
		} else {
			return false;
		}
	}

	private boolean validate(int x, int y, int n0) {
		int n = getPotential(x, y);
		if (n == 0 || n > n0) {
			return false;
		}

		int n1 = getPotential(x, y - 1);
		n1 = Math.max(n1, getPotential(x + 1, y));
		n1 = Math.max(n1, getPotential(x, y + 1));
		n1 = Math.max(n1, getPotential(x - 1, y));

		if (n1 <= n) {
			return updatePotential(x, y, Math.max(n1 - 1, 0));
		} else {
			return false;
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m_potentialTable.length; i++) {
			sb.append(Integer.toString(m_potentialTable[i], 36));
			if ((i + 1) % m_tableWidth == 0) {
				sb.append("\n");
			}
		}
		return sb.toString();
	}

	public int getPossibleArea() {
		return m_possibleArea;
	}

	public int getNumOfCellsPerPotential(int potential) {
		return m_cellsPerPotential[potential - 1].size();
	}

	public boolean confirm(int x0, int y0) {
		boolean isChanged = false;
		isChanged |= confirmPreliminary(x0, y0);

		long combinationBits = 0;
		for (Collection<Pnt> cells : m_cellsPerPotential) {
			combinationBits += cells.size() - 1;
		}
		if (combinationBits < 4) {
			isChanged |= confirmPrecisely(x0, y0);
		}
		return isChanged;
	}

	public boolean confirmPrecisely(int x0, int y0) {
		assert getPotential(x0, y0) != 0;

		ShimaShapePredictor predictor = new ShimaShapePredictor(this);

		List<List<Pnt>> shapes = predictor.predict();
		if (shapes == null) {
			return false;
		}

		Set<Pnt> reachableCells = new HashSet<Pnt>();

		Pnt p0 = new Pnt(x0, y0);

		for (List<Pnt> shape : shapes) {
			if (shape.contains(p0)) {
				reachableCells.addAll(shape);
			}
		}

		boolean isChanged = false;
		for (List<Pnt> cells : m_cellsPerPotential) {
			for (int i = 0; i < cells.size(); i++) {
				Pnt p = cells.get(i);
				if (!reachableCells.contains(p)) {
					isChanged |= updatePotential(p.x, p.y, 0);
				}

			}
		}
		return isChanged;

	}

	private static class ShimaShapePredictor {
		private ShimaPotential that;

		public ShimaShapePredictor(ShimaPotential potential) {
			that = potential;
		}

		public List<List<Pnt>> predict() {
			List<Pnt> shape = new ArrayList<Pnt>();
			shape.add(new Pnt(0, 0));
			List<List<Pnt>> result = new ArrayList<List<Pnt>>();
			expand(shape, that.m_number - 1, that, result);
			return result;
		}

		private void expand(List<Pnt> shape, int n, ShimaPotential t, List<List<Pnt>> result) {
			if (shape.size() == t.m_number) {
				CollectionUtil.addOnce(result, shape);
				return;
			}

			if (n == 0) {
				return;
			}

			List<Pnt> neighbors = getNeighborCells(shape, n, t);

			if (neighbors.size() == 0) {
				// just go deeper
				expand(shape, n - 1, t, result);
			}

			int maxCombination = 1 << neighbors.size();
			for (int combination = 1; combination < maxCombination; combination++) {
				if (NumberUtil.countBits(combination) > t.m_number - shape.size()) {
					continue;
				}
				List<Pnt> newShape = new ArrayList<Pnt>(shape);
				ShimaPotential newPotential = t.dup();
				int mask = 1;
				for (int i = 0; i < neighbors.size(); i++) {
					Pnt p = neighbors.get(i);
					if ((combination & mask) != 0) {
						newShape.add(p);
					} else {
						newPotential.updatePotential(p.x, p.y, 0);
					}
					mask <<= 1;
				}

				expand(newShape, n - 1, newPotential, result);
			}
		}

		private List<Pnt> getNeighborCells(List<Pnt> shape, int n, ShimaPotential t) {
			List<Pnt> result = new ArrayList<Pnt>();
			for (Pnt p0 : t.m_cellsPerPotential[n - 1]) {
				for (Direction d : Direction.CLOCKWISE4) {
					Pnt p1 = p0.add(d.v);
					if (shape.contains(p1)) {
						CollectionUtil.addOnce(result, p0);
						break;
					}
				}
			}

			return result;
		}
	}

	public boolean confirmPreliminary(int x, int y) {
		int n = getPotential(x, y);
		boolean[] walked = new boolean[m_tableWidth * m_tableWidth];
		int[] locallyWalked = new int[m_tableWidth * m_tableWidth];

		walk(x, y, n, walked, locallyWalked);

		boolean isChanged = false;
		for (List<Pnt> cells : m_cellsPerPotential) {
			for (int i = 0; i < cells.size(); i++) {
				Pnt p = cells.get(i);
				int pi = p.x + p.y * m_tableWidth + m_tableCener;
				if (getPotential(p.x, p.y) != 0 && !walked[pi]) {
					isChanged |= updatePotential(p.x, p.y, 0);
				}
			}
		}
		return isChanged;
	}

	private void walk(int x, int y, int leg, boolean[] walked, int[] locallyWalked) {
		Arrays.fill(locallyWalked, 0);
		walkLeg(x, y, leg, walked, locallyWalked);

		int n0 = getPotential(x, y);
		for (Direction d : Direction.CLOCKWISE4) {
			int x1 = x + d.v.dx;
			int y1 = y + d.v.dy;
			int n = getPotential(x1, y1);
			if (n > n0) {
				walk(x1, y1, leg, walked, locallyWalked);
			}
		}
	}

	private void walkLeg(int x, int y, int leg, boolean[] walked, int[] locallyWalked) {

		if (getPotential(x, y) == 0) {
			return;
		}

		int i = x + y * m_tableWidth + m_tableCener;
		if (locallyWalked[i] >= leg) {
			return;
		}

		locallyWalked[i] = leg;
		walked[i] = true;

		if (leg == 0) {
			return;
		}

		for (Direction d : Direction.CLOCKWISE4) {
			walkLeg(x + d.v.dx, y + d.v.dy, leg - 1, walked, locallyWalked);
		}
	}

	public Collection<Pnt>[] getCellsPerPotential() {
		return m_cellsPerPotential;
	}

}
